Recursive Algorithm: Algorithm that calls itself


Example: Compute sum of first n positive integers
Write with loop and with recursion [Sum.java]


Example: Print out number
Write with loop and with recursion [PrintNum.java]


Rules of Recursion:
(1) One or more base cases that can be solved without recursion
(2) Each recursive call makes progress towards a base case (i.e., the recursion will eventually terminate or "bottom out")


Example: Searching for folders/files with a particular name (recursive data)
Write
What is the base case?
Why does each recursive call make progress toward the base case?


Example: Sorting a pile of exams by name (divide-and-conquer)
Write pseudo-code
What is the base case?
Why does each recursive call make progress toward the base case?


Example: Searching for all words that can be formed from a set of characters (backtracking search)
Describe basic approach
	Select any character
	Check to see if it's a word
	Select any unused character and append to the first
	Check to see if it's a word
	Select any unused character and append to the first two
	Check to see if it's a word
	Stop when all characters have been used
	Backtrack and try characters in a different order
Write [RecursiveWordSearch.java]
What is the base case?
Why does each recursive call make progress toward the base case?


Example: Recursive Maze Solver
Show pseudo-code in RecursiveMazeAlgorithm.txt
	Review iterative algorithm, explain recursive algorithm


When to use recursion:

(1) Recursive Data

Folder = File* + Folder*

Program source code is recursive.  Compilers use recursion to process source code (e.g., syntax checking)

Arithmetic expressions in a programming language:
E = integer constant | floating point constant | variable |
	E + E, E – E, E * E, E / E, -E, (E)

Statements in a programming language:
S = E | return; | break; | continue; | E = E | E.method(E, E, …) |
while (E) S; | if (E) S else S | { S; S; …, S; } | …


(2) Divide-and-Conquer
SolveProblem(P)
	if (P is small and can be solved directly)
		Solve P directly
	else
		Divide P into smaller sub-problems p1, p2, ..., pn
		SolveProblem(p1);
		SolveProblem(p2);
		...
		SolveProblem(pn);
		Combine solutions to p1, p2, ..., pn to create a solution for P
	return solution for P


(3) Backtracking Search
	WordSearch, Maze Solver, Boggle